1. Field of the Invention
The invention relates generally to the classification and/or filtering of data packets, and more specifically to the high speed filtering and/or classification of data packets.
2. Background Information
In a communications network, there is a well-recognized need to classify information units, such as packets, that are passed between the various network devices in the network, e.g., routers and switches, in order to support a wide range of applications, such as security control, packet filtering, Class of Service (CoS) and Quality of Service (QoS). Often in such networks, these network devices use access control lists (ACLs) to, inter alia, classify packets for these applications.
An ACL typically comprises an ordered list of access control entries (ACEs), i.e., rules, where each rule defines a pattern (criterion) that is compared with received packets. The pattern could specify a particular source or destination address, a protocol or some other field that is looked for in the packet. For example, the pattern might be defined to look for a specific protocol in the packet's header such as, the Transmission Control Protocol (TCP) or the Internet Protocol (IP). The pattern is used to determine if the rule applies to the packet. If the pattern is found in the packet, the rule is said to apply to the packet.
Associated with each rule is an action that specifies the act to be taken if the rule applies. In its simplest form, this action may be to allow the matched packet to proceed towards its destination, i.e., “permit,” or to stop the packet from proceeding any further, i.e., “deny.” Conversely, if there is no match to any of the ACL's rules, the action may be to drop the packet, i.e., “a final deny.” In a more sophisticated form, complex policies and filtering rules may be implemented in the ACL to determine the course of the data packet.
Typically, a packet is classified by searching for the first rule in the ACL that applies to the packet. The number of rules involved and the amount of processing time needed to make this determination often depends on the approach taken. For example, one approach would be to run through the list of rules starting from the first rule in the list and continuing towards the last rule in the list until a matching rule, i.e., a rule that applies to the packet, is found. This approach is simple, but is not very efficient. For example, the time spent processing each packet may vary depending on the packet. Packets that meet the criteria associated with rules earlier in the list will be processed faster than packets that meet criteria associated with rules that are positioned farther down the list.
One approach to obtaining an overall faster processing of packets is to predetermine the frequency of the matching of the various rules and to place the most selected rules at the top of the list. However, this method is highly dependent on the packet mix and is not very efficient should this mix change. Another approach would be to implement a technique whereby packets are classified using a predetermined number of lookup operations such as described in commonly owned co-pending U.S. patent application Ser. No. 09/557,480, now issued as U.S. Pat. No. 6,970,462, titled, “A Method for High Speed Packet Classification,” which was filed on Apr. 24, 2000, by Andrew McRae and hereinafter referred to as “McRae.”
McRae describes a technique whereby a packet's header is divided into sections. These sections are applied to a hierarchy of lookup tables that represent all possible combinations of matching rules for all values of the packet header sections to determine an outcome such as, e.g., a first matching rule that applies to the packet. These lookup tables must exist before a packet can be classified. Computing resources, such as processor time and memory, needed to generate these lookup tables depends in part on the number of rules in the ACL. Generally, as the number of rules in the ACL increases, the computing resources needed to build and hold the lookup tables increases. In systems where computing resources are limited, the number of rules that the technique can support may be limited due to the limited resources available.